package 剑指Offer专项突破;

import test0ne.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Algo44 {


    /**
     * 每一层最大值
     * 层序遍历，队列
     * @param root
     * @return
     */
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if(root == null) {
            return result;
        }
        LinkedList<TreeNode> linkedList = new LinkedList<>();

        int cur = 1;
        int next = 0;
        int max = Integer.MIN_VALUE;
        linkedList.offer(root);
        while (!linkedList.isEmpty()) {
            TreeNode t = linkedList.poll();
            max = Math.max(max, t.val);
            if(t.left != null) {
                linkedList.offer(t.left);
                next++;
            }
            if(t.right != null) {
                linkedList.offer(t.right);
                next++;
            }
            cur--;
            if(cur == 0) {
                cur = next;
                next = 0;
                result.add(max);
                max = Integer.MIN_VALUE;
            }
        }
        return result;
    }


    /**
     * Algo_45 二叉树最底层最左边的值
     * @param root
     * @return
     */
    public int findBottomLeftValue(TreeNode root) {
        LinkedList<TreeNode> linkedList = new LinkedList<>();

        int cur = 1;
        int next = 0;
        int left = Integer.MIN_VALUE;
        boolean has = false;
        linkedList.offer(root);
        while (!linkedList.isEmpty()) {
            TreeNode t = linkedList.poll();
            if(!has) {
                left = t.val;
                has = true;
            }
            if(t.left != null) {
                linkedList.offer(t.left);
                next++;
            }
            if(t.right != null) {
                linkedList.offer(t.right);
                next++;
            }
            cur--;
            if(cur == 0 && !linkedList.isEmpty()) {
                has = false;
                cur = next;
                next = 0;
            }
        }
        return left;
    }

    /**
     * Algo46  二叉树的右侧试图
     * 层序遍历，每层拿最后一个
     * @param root
     * @return
     */
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if(root == null) {
            return result;
        }
        LinkedList<TreeNode> linkedList = new LinkedList<>();

        int cur = 1;
        int next = 0;
        int right;
        linkedList.offer(root);
        while (!linkedList.isEmpty()) {
            TreeNode t = linkedList.poll();
            right = t.val;
            if(t.left != null) {
                linkedList.offer(t.left);
                next++;
            }
            if(t.right != null) {
                linkedList.offer(t.right);
                next++;
            }
            cur--;
            if(cur == 0) {
                cur = next;
                next = 0;
                result.add(right);
            }
        }
        return result;
    }
}
